package com.cat.dataStructure03;

import java.util.Arrays;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/minimum-edge-weight-equilibrium-queries-in-a-tree/
 * @create 2025/11/21 10:14
 * @since JDK17
 */

public class Solution96 {
    static int MAXN = 10001, MAXQ = 20001, tcnt, qcnt, MAXW = 26, n, m;
    static int[] headTree = new int[MAXN], nextTree = new int[MAXN << 1], toTree = new int[MAXN << 1], val = new int[MAXN << 1];
    static int[] f = new int[MAXN], lca = new int[MAXQ << 1];
    static int[][] h = new int[MAXN][MAXW + 1];
    static int[] headQuery = new int[MAXQ], nextQuery = new int[MAXQ << 1], toQuery = new int[MAXQ << 1], query = new int[MAXQ << 1];
    static boolean[] vis = new boolean[MAXN];

    static void build() {
        qcnt = tcnt = 1;
        Arrays.fill(headTree, 0, n, 0);
        Arrays.fill(headQuery, 0, n, 0);
        Arrays.fill(vis, 0, n, false);
        for (int i = 0; i < n; i++) {
            f[i] = i;
        }
    }
    static int find(int x) {
        if (f[x] != x) {
            f[x] = find(f[x]);
        }
        return f[x];
    }

    static void addEdge(int u, int v, int w) {
        nextTree[tcnt] = headTree[u];
        toTree[tcnt] = v;
        val[tcnt] = w;
        headTree[u] = tcnt++;
    }
    static void addQuery(int u, int v, int i) {
        nextQuery[qcnt] = headQuery[u];
        toQuery[qcnt] = v;
        query[qcnt] = i;
        headQuery[u] = qcnt++;
    }
    static void dfs(int u, int f, int w) { // 生成从头到当前节点的边权
        if (u == 0) {
            Arrays.fill(h[0], 0);
        } else {
            for (int i = 1; i <= MAXW; i++) {
                h[u][i] = h[f][i];
            }
            h[u][w]++;
        }
        for (int e = headTree[u]; e != 0; e = nextTree[e]) {
            if (toTree[e] != f) {
                dfs(toTree[e], u, val[e]);
            }
        }
    }
    static void tarjan(int u, int fa) {
        vis[u] = true;
        for (int e = headTree[u]; e != 0; e = nextTree[e]) {    //
            if (toTree[e] != fa) {
                tarjan(toTree[e], u);
            }
        }
        for (int e = headQuery[u]; e != 0; e = nextQuery[e]) {
            if (vis[toQuery[e]]) { // 没有遇到过
                lca[query[e]] = find(toQuery[e]);
            }
        }
        f[u] = fa;
    }

    public int[] minOperationsQueries(int n, int[][] edges, int[][] queries) {
        this.n = n;
        build();
        for (var e : edges) {
            addEdge(e[0], e[1], e[2]);
            addEdge(e[1], e[0], e[2]);
        }
        dfs(0, 0, -1);
        int m = queries.length;
        int[] ans = new int[m];
        for (int i = 0; i < m; i++) {
            var q = queries[i];
            addQuery(q[0], q[1], i);
            addQuery(q[1], q[0], i);
        }
        tarjan(0, 0);
        for (int i = 0; i < m; i++) {
            int max = 0, allCnt = 0, a = queries[i][0], b = queries[i][1], c = lca[i], wcnt = 0;
            for (int j = 1; j <= MAXW; j++) {
                wcnt = h[a][j] + h[b][j] - 2 * h[c][j];
                max = Math.max(max, wcnt);
                allCnt += wcnt;
            }
            ans[i] = allCnt - max;
        }

        return ans;
    }
}
